package dp;

public class _10_1049_最后一块石头的重量Ⅱ_滚动数组 {
    public static int lastStoneWeightII(int[] stones) {
    	int sum = 0;
    	for(int i = 0; i < stones.length; i++) {
    		sum += stones[i];
    	}
    	// 拆分两堆石头
    	int mid = sum/2; // 第一堆石头
    	int dp[] = new int[mid+1];

    	for(int i = 1; i <= stones.length; i++) {
    		for(int j = mid; j >= stones[i-1]; j--) {
    			dp[j] = Math.max(dp[j], dp[j-stones[i-1]] + stones[i-1]);
    		}
    	}
    	
    	int other = sum - dp[mid];
    	
    	return other - dp[mid];
    }
    public static void main(String[] args) {
    	int stones[] = {2,7,4,1,8,1};
		System.out.println(lastStoneWeightII(stones));
	}
}
